#include <iostream>
#include <vector>
using namespace std;

class Solution_do {
    public:
	vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k)
	{
                int n = nums.size();
                nums.push_back(0);
                vector<vector<int>> suffix(n, vector<int>(n, 0));
                vector<vector<int>> pos(n, vector<int>(n, 0));
                vector<vector<int>> dp(3, vector<int>(n, 0));
                vector<vector<int>> bk(3, vector<int>(n, 0));

                int sum = 0;
                for(int i = 0; i < k; i++){
                        sum += nums[i];
                }
                suffix[0][k - 1] = sum;
                int max_sum = sum;
                int next_sum = sum;

                for(int i = 0; i <= n - k; i++){
                        sum = next_sum;
                        max_sum = sum;
                        suffix[i][i + k - 1] = max_sum;
                        pos[i][i + k - 1] = i;
                        for(int j = i + k; j < n; j++){
                                sum += nums[j] - nums[j - k];
                                if(sum > max_sum){
                                        pos[i][j] = j - k + 1;
                                }else{
                                        pos[i][j] = pos[i][j - 1];
                                }
                                max_sum = max(sum, max_sum);
                                suffix[i][j] = max_sum;
                        }
                        next_sum += nums[i + k] - nums[i];
                }

                for(int i = 0; i < n; i++){
                        dp[0][i] = suffix[0][i];
                }

                for(int i = 1; i < 3; i++){
                        for(int j = 1; j < n; j++){
                                for(int l = k; l <= j; l++){
                                        int val = dp[i - 1][l - 1] + suffix[l][j];
                                        if(val > dp[i][j]){
                                                bk[i][j] = l;
                                        }
                                        dp[i][j] = max(val, dp[i][j]);
                                }
                        }
                }


                int n2 = bk[2][n - 1];
                int pos1 = pos[n2][n - 1];

                int n3 = bk[1][n2 - 1];
                int pos2 = pos[n3][n2 - 1];

                int pos3 = pos[0][n3 - 1];


                
                return { pos3, pos2, pos1 };
	}
};

class Solution {
    public:
	vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k)
	{
                int n = nums.size();
                vector<int> sum(n, 0);
                int k_sum = 0;
                for(int l = 0, r = k - 1; l < n; l++, r++){
                        k_sum += nums[l];
                        if(l >= k - 1){
                                sum[l - k + 1] = k_sum;
                                k_sum -= nums[l - k + 1];
                        }
                }

                vector<int> prefix(n, 0);
                for(int i = k; i < n; i++){
                        prefix[i] =  sum[i - k + 1] > sum[prefix[i - 1]] ? i - k + 1 : prefix[i - 1];
                }

                vector<int> suffix(n, 0);
                suffix[n - k] = n - k;
                for(int i = n - k - 1; i >= 0; i--){
                        suffix[i] = sum[i] >=  sum[suffix[i + 1]] ? i : suffix[i + 1];
                }

                k_sum = 0;
                for(int i = k; i <= 2*k - 1; i++){
                        k_sum += nums[i];
                }

                int ans, left, mid, right, max_k_sum = INT32_MIN;
                for(int l = k, r = l + k -1; r < n - k; l++, r++){
                        if((ans = k_sum + sum[prefix[l - 1]] + sum[suffix[r + 1]]) > max_k_sum){
                                left = prefix[l - 1];
                                mid = l;
                                right = suffix[r + 1];
                                max_k_sum = ans;
                        }
                        k_sum -= nums[l];
                        k_sum += nums[r + 1];
                }

                return {left, mid, right};
        }
};

int main()
{
	vector<int> nums = { 7,13,20,19,19,2,10,1,1,19 };
	int k = 3;
	vector<int> ans = Solution().maxSumOfThreeSubarrays(nums, k);
        for(int val : ans){
                cout<<val<<" ";
        }
        cout<<endl;
	return 0;
}